@inproceedings{NanongkaiDP11,
  author    = {Danupon Nanongkai and
               Atish {Das Sarma} and
               Gopal Pandurangan},
  title     = {A tight unconditional lower bound on distributed randomwalk
               computation},
  booktitle = {PODC},
  year      = {2011},
  pages     = {257-266},
  ee        = {http://doi.acm.org/10.1145/1993806.1993853},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{BBF04,
  author    = {Thibault Bernard and
               Alain Bui and
               Olivier Flauzac},
  title     = {Random Distributed Self-stabilizing Structures Maintenance},
  booktitle = {ISSADS},
  year      = {2004},
  pages     = {231-240}
}


@inproceedings{ElsasserS09,
  author    = {Robert Els{\"a}sser and
               Thomas Sauerwald},
  title     = {Tight Bounds for the Cover Time of Multiple Random Walks},
  booktitle = {ICALP (1)},
  year      = {2009},
  pages     = {415-426}}
}

@inproceedings{broder,
 author = {A. Broder},
 title = {Generating Random Spanning Trees},
 booktitle = {FOCS},
 year = {1989}
 }

 inproceedings{bar-ilan,
 author = {J. Bar-Ilan and D. Zernik},
 title = {Random Leaders and Random Spanning Trees},
 booktitle = {3rd International Workshop on Distributed Algorithms (later called DISC)},
 year = {1989}
 }

@inproceedings{bar-ilan,
  author    = {Judit Bar-Ilan and
               Dror Zernik},
  title     = {Random Leaders and Random Spanning Trees},
  booktitle = {WDAG (later called DISC)},
  year      = {1989},
  pages     = {1-12},
  ee        = {http://dx.doi.org/10.1007/3-540-51687-5_27},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


inproceedings{BIZ89,
 author = {Judit Bar-Ilan and Dror Zernik},
 title = {Random Leaders and Random Spanning Trees},
 booktitle = {Proceedings of the 3rd International Workshop on Distributed Algorithms},
 year = {1989},
 isbn = {3-540-51687-5},
 pages = {1--12},
 publisher = {Springer-Verlag},
 address = {London, UK},
 }

@article{Baala,
  author    = {Hichem Baala and
               Olivier Flauzac and
               Jaafar Gaber and
               Marc Bui and
               Tarek A. El-Ghazawi},
  title     = {A self-stabilizing distributed algorithm for spanning tree
               construction in wireless ad hoc networks},
  journal   = {J. Parallel Distrib. Comput.},
  volume    = {63},
  number    = {1},
  year      = {2003},
  pages     = {97-104}}


@article{aldous,
  author    = {David Aldous},
  title     = {The Random Walk Construction of Uniform Spanning Trees and
               Uniform Labelled Trees},
  journal   = {SIAM J. Discrete Math.},
  volume    = {3},
  number    = {4},
  year      = {1990},
  pages     = {450-465}
}



 @inproceedings{aleliunas,
 author = {R. Aleliunas and R.M. Karp and R.J. Lipton and L. Lovasz and C. Rackoff},
 title = {Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems},
 booktitle = {FOCS},
 year = {1979}
 }

 @inproceedings{goyal,
 author = {N. Goyal and L. Rademacher and S. Vempala},
 title = {Expanders via Random Spanning Trees},
 booktitle = {SODA},
 year = {2009}
 }

 @article{peleg-mst,
    author = "J. Garay and S. Kutten and D. Peleg",
    title = "A sublinear time distributed algorithm for minimum-weight spanning trees",
    journal = {SIAM J. Comput.},
    year = {1998},
    volume = {27},
    pages = {302--316}
}

@article{MP,
 author = {S. Muthukrishnan and Gopal Pandurangan},
 title = {Thresholding Random Geometric Properties Motivated by Ad Hoc Sensor Networks},
 journal = {Journal of Computer and System Sciences},
 year = {2010},
pages = {686-696},
volume = {76(7)}
 }


@inproceedings{kelner-madry,
 author = {J. Kelner and A. Madry},
 title = {Faster Generation of Random Spanning Trees},
 booktitle = {IEEE FOCS},
 year = {2009},
 address = {Atlanta, GA, USA},
 publisher = {IEEE}
 }

@InProceedings{mihail-topaware,
  author =   {C. Gkantsidis and G. Goel and M. Mihail and A. Saberi},
  title =    {Towards Topology Aware Networks},
  booktitle =    {IEEE INFOCOM},
  year =     {2007}
}

@article{elkin-survey,
    author = "M. Elkin",
    title = "An Overview of Distributed Approximation",
    journal = {ACM SIGACT News Distributed Computing Column},
    year = {2004},
    month = {December},
    volume = {35},
    number = {4},
    pages = {40--57}
}

@incollection{dubhashi,
author = {Devdatt P. Dubhashi and Fabrizio Grandioni and Alessandro Panconesi},
title  = {{Distributed Algorithms via LP Duality and Randomization}},
booktitle  =  "Handbook of Approximation Algorithms and Metaheuristics",
publisher = "Chapman and Hall/CRC",
year =  2007
}

@article{khan-disc,
 author = {M. Khan and G. Pandurangan},
 title = {A Fast Distributed Approximation Algorithm for Minimum Spanning Trees},
 journal = {Distributed Computing},
 year = {2008},
 volume = {20},
 pages = {391-402}
}

@inproceedings{khan-podc,
  author    = {Maleq Khan and
               Fabian Kuhn and
               Dahlia Malkhi and
               Gopal Pandurangan and
               Kunal Talwar},
  title     = {Efficient distributed approximation algorithms via probabilistic
               tree embeddings},
  booktitle = {PODC},
  year      = {2008},
  pages     = {263-272}}
}

@article{kutten-domset,
    author = "S. Kutten and D. Peleg",
    title = "Fast distributed construction of k-dominating sets and applications",
    journal = {J. Algorithms},
    year = {1998},
    volume = {28},
    pages = {40--66}
}

@article{kempe,
author = {D. Kempe and F. McSherry},
title=  {A Decentralized Algorithm for Spectral Analysis},
 journal = {Journal of
Computer and System Sciences},
volume = {74(1)},
year = {2008},
pages = {70-83}
}


@inproceedings{BFFKRW,
  author    = {Tugkan Batu and
               Lance Fortnow and
               Eldar Fischer and
               Ravi Kumar and
               Ronitt Rubinfeld and
               Patrick White},
  title     = {Testing Random Variables for Independence and Identity},
  booktitle = {FOCS},
  year      = {2001},
  pages     = {442-451}
}

@Article{JS89,
  author =   {M. Jerrum and A. Sinclair},
  title =    {Approximating the permanent},
  journal =      {SIAM Journal of Computing},
  year =     {1989},
  volume =   {18},
  number =   {6},
  pages =    {1149--1178}
}

@misc{LPW,
  title={{Markov chains and mixing times}},
  author={Levin, D.A. and Y.(Yuval) Peres and Elizabeth L.(Elizabeth Lee) Wilmer},
  year={2009},
  publisher={American Mathematical Society}
}

@article{Lyons,
  author    = {Russell Lyons},
  title     = {Asymptotic Enumeration of Spanning Trees},
  journal   = {Combinatorics, Probability {\&} Computing},
  volume    = {14},
  number    = {4},
  year      = {2005},
  pages     = {491-522},
  ee        = {http://dx.doi.org/10.1017/S096354830500684X},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Vitter85,
  author    = {Jeffrey Scott Vitter},
  title     = {Random Sampling with a Reservoir},
  journal   = {ACM Trans. Math. Softw.},
  volume    = {11},
  number    = {1},
  year      = {1985},
  pages     = {37-57},
  note      = {Also appeared in FOCS'83},
  ee        = {http://doi.acm.org/10.1145/3147.3165},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@INPROCEEDINGS(mihail,
 author =     {C. Gkantsidis and  M. Mihail and A. Saberi},
 title =       {Throughput and Congestion in Power-Law Graphs},
booktitle = {SIGMETRICS},
 pages =       {148-159},
  year =     {2003}
  )

@article(dinwoodie,
author = {I. H. Dinwoodie},
title = {A Probability Inequality for the Occupation Measure of a Reversible Markov Chain},
journal = {The Annals of Applied Probability},
volume = {5(1)},
year =  {1995},
pages = {37-43}
)

@article{elkin,
  author    = {Michael Elkin},
  title     = {An Unconditional Lower Bound on the Time-Approximation Trade-off
               for the Distributed Minimum Spanning Tree Problem},
  journal   = {SIAM J. Comput.},
  volume    = {36},
  number    = {2},
  year      = {2006},
  pages     = {433-456},
  note      = {Also appeared in STOC'04},
  ee        = {http://dx.doi.org/10.1137/S0097539704441058},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@inproceedings{DNP09-podc,
  author    = {Atish {Das Sarma} and
               Danupon Nanongkai and
               Gopal Pandurangan},
  title     = {Fast distributed random walks},
  booktitle = {PODC},
  year      = {2009},
  pages     = {161-170}
}

@inproceedings{DNPT10-podc,
  author    = {Atish {Das Sarma} and
               Danupon Nanongkai and
               Gopal Pandurangan and
               Prasad Tetali},
  title     = {Efficient Distributed Random Walks with Applications},
  booktitle = {PODC},
  year      = {2010}
}


BOOK(lynch,
 author = {N. Lynch},
 title = {Distributed Algorithms},
 publisher = {Morgan Kaufmann Publishers, San Mateo, CA},
 year = {1996}
)

@book{lynch,
 author = {Lynch, Nancy A.},
 title = {Distributed Algorithms},
 year = {1996},
 isbn = {1558603484},
 publisher = {Morgan Kaufmann Publishers Inc.},
 address = {San Francisco, CA, USA},
}


@article{peleg-bound,
  author    = {David Peleg and
               Vitaly Rubinovich},
  title     = {A Near-Tight Lower Bound on the Time Complexity of Distributed
               Minimum-Weight Spanning Tree Construction},
  journal   = {SIAM J. Comput.},
  volume    = {30},
  number    = {5},
  year      = {2000},
  pages     = {1427-1442},
  note      = {Also in FOCS'99},
  ee        = {http://epubs.siam.org/sam-bin/dbq/article/36974},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{frieze,
    author = "C. Cooper and A. Frieze and T. Radzik",
    title = "Multiple random walks in random regular graphs",
    booktitle = "Preprint",
    year = "2009"
}


@article{Gillman98,
  author    = {David Gillman},
  title     = {A Chernoff Bound for Random Walks on Expander Graphs},
  journal   = {SIAM J. Comput.},
  volume    = {27},
  number    = {4},
  year      = {1998},
  pages     = {1203-1220},
  ee        = {http://epubs.siam.org/sam-bin/dbq/article/26876},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@article{Jonasson98,
  author    = {Johan Jonasson},
  title     = {On the Cover Time for Random Walks on Random Graphs},
  journal   = {Combinatorics, Probability {\&} Computing},
  volume    = {7},
  number    = {3},
  year      = {1998},
  pages     = {265-279}
}

@inproceedings{Wilson96,
  author    = {David Bruce Wilson},
  title     = {Generating Random Spanning Trees More Quickly than the Cover
               Time},
  booktitle = {STOC},
  year      = {1996},
  pages     = {296-303},
  ee        = {http://doi.acm.org/10.1145/237814.237880}
}


@ARTICLE{JS00,
    author = {Johan Jonasson and Oded Schramm},
    title = {On the cover time of planar graphs},
    journal = {Elec. Comm. Probab},
    year = {2000},
    volume = {5},
    pages = {85-90}
}

@inproceedings{CooperF03,
  author    = {Colin Cooper and
               Alan M. Frieze},
  title     = {The cover time of sparse random graphs},
  booktitle = {SODA},
  year      = {2003},
  pages     = {140-147},
  ee        = {http://doi.acm.org/10.1145/644108.644134}
}


@inproceedings{BroderK88,
  author    = {Andrei Z. Broder and
               Anna R. Karlin},
  title     = {Bounds on the Cover Time (Preliminary Version)},
  booktitle = {FOCS},
  year      = {1988},
  pages     = {479-487}
}


@inproceedings{ChandraRRST89,
  author    = {Ashok K. Chandra and
               Prabhakar Raghavan and
               Walter L. Ruzzo and
               Roman Smolensky and
               Prasoon Tiwari},
  title     = {The Electrical Resistance of a Graph Captures its Commute
               and Cover Times (Detailed Abstract)},
  booktitle = {STOC},
  year      = {1989},
  pages     = {574-586}
}


@article{ST08,
  author    = {Rahul Sami and
               Andy Twigg},
  title     = {Lower bounds for distributed markov chain problems},
  journal   = {CoRR},
  volume    = {abs/0810.5263},
  year      = {2008},
  ee        = {http://arxiv.org/abs/0810.5263}
}

@article{AHLP01,
  author    = {Lada A. Adamic and
               Rajan M. Lukose and
               Amit R. Puniyani and
               Bernardo A. Huberman},
  title     = {Search in Power-Law Networks},
  journal   = {Physical Review},
  volume    = {64},
  year      = {2001},
  ee        = {http://arxiv.org/abs/cs.NI/0103016}
}

@inproceedings{BAS04,
  author    = {Ashwin R. Bharambe and
               Mukesh Agrawal and
               Srinivasan Seshan},
  title     = {Mercury: supporting scalable multi-attribute range queries},
  booktitle = {SIGCOMM},
  year      = {2004},
  pages     = {353-366},
  ee        = {http://doi.acm.org/10.1145/1015467.1015507}
}

@inproceedings{LCCLS02,
  author    = {Qin Lv and
               Pei Cao and
               Edith Cohen and
               Kai Li and
               Scott Shenker},
  title     = {Search and replication in unstructured peer-to-peer networks},
  booktitle = {ICS},
  year      = {2002},
  pages     = {84-95},
 publisher = {ACM},
  address = {New York, NY, USA},
  ee        = {http://doi.acm.org/10.1145/514191.514206}
}

inproceedings{Lv:2002:SRU:514191.514206,
 author = {Lv, Qin and Cao, Pei and Cohen, Edith and Li, Kai and Shenker, Scott},
 title = {Search and replication in unstructured peer-to-peer networks},
 booktitle = {Proceedings of the 16th international conference on Supercomputing},
 series = {ICS '02},
 year = {2002},
 isbn = {1-58113-483-5},
 location = {New York, New York, USA},
 pages = {84--95},
 numpages = {12},
 url = {http://doi.acm.org/10.1145/514191.514206},
 doi = {http://doi.acm.org/10.1145/514191.514206},
 acmid = {514206},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {peer-to-peer, replication, search, unstructured},
}

@inproceedings{GMS05,
  author    = {Christos Gkantsidis and
               Milena Mihail and
               Amin Saberi},
  title     = {Hybrid search schemes for unstructured peer-to-peer networks},
  booktitle = {INFOCOM},
  year      = {2005},
  pages     = {1526-1537},
  ee        = {http://dx.doi.org/10.1109/INFCOM.2005.1498436}
}

@inproceedings{C05,
  author    = {Brian F. Cooper},
  title     = {Quickly Routing Searches Without Having to Move Content},
  booktitle = {IPTPS},
  year      = {2005},
  pages     = {163-172},
  ee        = {http://dx.doi.org/10.1007/11558989_15}
}


@article{ZS06,
  author    = {Ming Zhong and
               Kai Shen},
  title     = {Random walk based node sampling in self-organizing networks},
  journal   = {Operating Systems Review},
  volume    = {40},
  number    = {3},
  year      = {2006},
  pages     = {49-55},
  ee        = {http://doi.acm.org/10.1145/1151374.1151386}
}

@inproceedings{KKD01,
  author    = {David Kempe and
               Jon M. Kleinberg and
               Alan J. Demers},
  title     = {Spatial gossip and resource location protocols},
  booktitle = {STOC},
  year      = {2001},
  pages     = {163-172},
  address   = {Crete, Greece},
  publisher = {ACM},
  ee        = {http://doi.acm.org/10.1145/380752.380796}
}

@inproceedings{K00,
  author    = {Jon M. Kleinberg},
  title     = {The small-world phenomenon: an algorithmic perspective},
  booktitle = {STOC},
  year      = {2000},
  pages     = {163-170},
  address   = {Portland, Oregon, USA},
  publisher = {ACM},
  ee        = {http://doi.acm.org/10.1145/335305.335325}
}

@inproceedings{KR04,
  author    = {David R. Karger and
               Matthias Ruhl},
  title     = {Simple efficient load balancing algorithms for peer-to-peer
               systems},
  booktitle = {SPAA},
  year      = {2004},
  pages     = {36-43},
  ee        = {http://doi.acm.org/10.1145/1007912.1007919},
  address   = {Barcelona, Catalonia, Spain}
}



@inproceedings{ZSS05,
  author    = {Ming Zhong and
               Kai Shen and
               Joel I. Seiferas},
  title     = {Non-uniform random membership management in peer-to-peer
               networks},
  booktitle = {INFOCOM},
  year      = {2005},
  pages     = {1151-1161},
  ee        = {http://dx.doi.org/10.1109/INFCOM.2005.1498342},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{MRRT53,
    abstract = {A general method, suitable for fast computing machines, for investigating such properties as equations of state for substances consisting of interacting individual molecules is described. The method consists of a modified Monte Carlo integration over configuration space. Results for the two-dimensional rigid-sphere system have been obtained on the Los Alamos MANIAC and are presented here. These results are compared to the free volume equation of state and to a four-term virial coefficient expansion.
    The Journal of Chemical Physics is copyrighted by The American Institute of Physics.},
    author = {Metropolis, Nicholas   and Rosenbluth, Arianna  W.  and Rosenbluth, Marshall  N.  and Teller, Augusta  H.  and Teller, Edward  },
    citeulike-article-id = {531300},
    doi = {http://dx.doi.org/10.1063/1.1699114},
    journal = {The Journal of Chemical Physics},
    keywords = {annealing, simulated},
    number = {6},
    pages = {1087--1092},
    posted-at = {2007-07-12 12:49:56},
    priority = {2},
    publisher = {AIP},
    title = {Equation of State Calculations by Fast Computing Machines},
    url = {http://dx.doi.org/10.1063/1.1699114},
    volume = {21},
    year = {1953}
}

@article{Hastings70,
    abstract = {A generalization of the sampling method introduced by Metropolis et al. (1953) is presented along with an exposition of the relevant theory, techniques of application and methods and difficulties of assessing the error in Monte Carlo estimates. Examples of the methods, including the generation of random orthogonal matrices and potential applications of the methods to numerical problems arising in statistics, are discussed. 10.1093/biomet/57.1.97},
    author = {Hastings, W. K. },
    citeulike-article-id = {1015842},
    doi = {http://dx.doi.org/10.1093/biomet/57.1.97},
    journal = {Biometrika},
    keywords = {approximate-methods, bayesian},
    month = {April},
    number = {1},
    pages = {97--109},
    posted-at = {2008-10-31 16:19:43},
    priority = {2},
    title = {Monte Carlo sampling methods using Markov chains and their applications},
    url = {http://dx.doi.org/10.1093/biomet/57.1.97},
    volume = {57},
    year = {1970}
}

inproceedings{LawS03,
  author    = {Ching Law and
               Kai-Yeung Siu},
  title     = {Distributed Construction of Random Expander Networks},
  booktitle = {INFOCOM},
  year      = {2003},
  ee        = {http://www.ieee-infocom.org/2003/papers/52_02.PDF}
}

@inproceedings{LawS03,
  author    = {Ching Law and
               Kai-Yeung Siu},
  title     = {Distributed Construction of Random Expander Networks},
  booktitle = {INFOCOM},
  year      = {2003},
  ee        = {http://www.ieee-infocom.org/2003/papers/52_02.PDF},
  address   = {Cambridge, MA, USA},
  publisher = {IEEE},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@book{chung,
 author = {Fan Chung},
 title = {Spectral Graph Theory},
 year = {1997},
 publisher = {American Mathematical Society},
 address = {Providence, RI, USA}
 }


@book{peleg,
 author = {David Peleg},
 title = {Distributed computing: a locality-sensitive approach},
 year = {2000},
 isbn = {0-89871-464-8},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 }


@inproceedings{PK09,
  author    = {Gopal Pandurangan and Maleq Khan},
  title     = {Theory of Communication Networks},
  booktitle = {Algorithms and Theory of Computation Handbook, Second Edition},
  year      = {2009},
  PUBLISHER =    {CRC Press},
}




@inproceedings{AKL+79,
  author    = {Romas Aleliunas and
               Richard M. Karp and
               Richard J. Lipton and
               L{\'a}szl{\'o} Lov{\'a}sz and
               Charles Rackoff},
  title     = {Random Walks, Universal Traversal Sequences, and the Complexity
               of Maze Problems},
  booktitle = {FOCS},
  year      = {1979},
  pages     = {218-223}
}



@article{BFG+03,
 author = {H. Baala and O. Flauzac and J. Gaber and M. Bui and T. El-Ghazawi},
 title = {A self-stabilizing distributed algorithm for spanning tree construction in wireless ad hoc networks},
 journal = {J. Parallel Distrib. Comput.},
 volume = {63},
 number = {1},
 year = {2003},
 issn = {0743-7315},
 pages = {97--104},
 doi = {http://dx.doi.org/10.1016/S0743-7315(02)00028-X},
 publisher = {Academic Press, Inc.},
 address = {Orlando, FL, USA},
 }

@inproceedings{GoyalRV09,
  author    = {Navin Goyal and
               Luis Rademacher and
               Santosh Vempala},
  title     = {Expanders via random spanning trees},
  booktitle = {SODA},
  year      = {2009},
  pages     = {576-585},
  ee        = {http://doi.acm.org/10.1145/1496770.1496834}
}

@inproceedings{LKRG03,
  author    = {Dmitri Loguinov and
               Anuj Kumar and
               Vivek Rai and
               Sai Ganesh},
  title     = {Graph-theoretic analysis of structured peer-to-peer systems:
               routing distances and fault resilience},
  booktitle = {SIGCOMM},
  year      = {2003},
  pages     = {395-406},
  publisher = {ACM},
  address = {New York, NY, USA},
  ee        = {http://doi.acm.org/10.1145/863955.863999}
}



@inproceedings{AAKKLT,
  author    = {Noga Alon and
               Chen Avin and
               Michal Kouck{\'y} and
               Gady Kozma and
               Zvi Lotker and
               Mark R. Tuttle},
  title     = {Many random walks are faster than one},
  booktitle = {SPAA},
  year      = {2008},
  pages     = {119-128},
  ee        = {http://doi.acm.org/10.1145/1378533.1378557}
}


@INPROCEEDINGS(costsens,
author = {B. Awerbuch and A. Baratz and D. Peleg},
 title = {Cost-sensitive analysis of communication protocols},
booktitle =  {  9th ACM PODC},
 pages = {177-187},
 year ={ 1990}
 )

@article{AP92,
 author = {Baruch Awerbuch and David Peleg},
 title = {Routing with polynomial communication-space trade-off},
 journal = {SIAM J. Discret. Math.},
 volume = {5},
 number = {2},
 year = {1992},
 issn = {0895-4801},
 pages = {151--162},
 doi = {http://dx.doi.org/10.1137/0405013},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 }

@inproceedings{AtishGP08,
  author    = {Atish {Das Sarma} and
               Sreenivas Gollapudi and
               Rina Panigrahy},
  title     = {Estimating PageRank on graph streams},
  booktitle = {PODS},
  year      = {2008},
  pages     = {69-78},
  ee        = {http://doi.acm.org/10.1145/1376916.1376928}
}


@book{MU-book-05,
 author = {Michael Mitzenmacher and Eli Upfal},
 title = {Probability and Computing: Randomized Algorithms and Probabilistic Analysis},
 year = {2005},
 isbn = {0521835402},
 publisher = {Cambridge University Press},
 address = {New York, NY, USA},
 }

@inproceedings{IJ90,
  author    = {Amos Israeli and
               Marc Jalfon},
  title     = {Token Management Schemes and Random Walks Yield Self-Stabilizing
               Mutual Exclusion},
  booktitle = {PODC},
  year      = {1990},
  pages     = {119-131},
  ee        = {http://doi.acm.org/10.1145/93385.93409}
}



@article{CTW93,
 author = {Don Coppersmith and Prasad Tetali and Peter Winkler},
 title = {Collisions among random walks on a graph},
 journal = {SIAM J. Discret. Math.},
 volume = {6},
 number = {3},
 year = {1993},
 issn = {0895-4801},
 pages = {363--374},
 doi = {http://dx.doi.org/10.1137/0406029},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 }

@article{DSW06,
  author    = {Shlomi Dolev and
               Elad Schiller and
               Jennifer L. Welch},
  title     = {Random Walk for Self-Stabilizing Group Communication in
               Ad Hoc Networks},
  journal   = {IEEE Trans. Mob. Comput.},
  volume    = {5},
  number    = {7},
  year      = {2006},
  pages     = {893-905},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/TMC.2006.104},
  note      = {also in PODC'02}
}


@inproceedings{DSW02,
  author    = {Shlomi Dolev and
               Elad Schiller and
               Jennifer L. Welch},
  title     = {Random walk for self-stabilitzing group communication in
               ad hoc networks},
  booktitle = {PODC},
  year      = {2002},
  pages     = {259},
  ee        = {http://doi.acm.org/10.1145/571825.571872}
}

@inproceedings{DolevT10,
  author    = {Shlomi Dolev and
               Nir Tzachar},
  title     = {Spanders: distributed spanning expanders},
  booktitle = {SAC},
  year      = {2010},
  pages     = {1309-1314}
}


@inproceedings{Broder89,
  author    = {Andrei Z. Broder},
  title     = {Generating Random Spanning Trees},
  booktitle = {FOCS},
  year      = {1989},
  pages     = {442-447}
}


@inproceedings{BBSB04,
  author    = {Marc Bui and
               Thibault Bernard and
               Devan Sohier and
               Alain Bui},
  title     = {Random Walks in Distributed Computing: A Survey},
  booktitle = {IICS},
  year      = {2004},
  pages     = {1-14},
  ee        = {http://dx.doi.org/10.1007/11553762_1}
}

@inproceedings{MG07,
  author    = {Rams{\'e}s Morales and
               Indranil Gupta},
  title     = {AVMON: Optimal and Scalable Discovery of Consistent Availability
               Monitoring Overlays for Distributed Systems},
  booktitle = {ICDCS},
  year      = {2007},
  pages     = {55},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/ICDCS.2007.87}
  }


 @article{GKM03,
 author = {Ayalvadi J. Ganesh and Anne-Marie Kermarrec and Laurent Massouli\'{e}},
 title = {Peer-to-Peer Membership Management for Gossip-Based Protocols},
 journal = {IEEE Trans. Comput.},
 volume = {52},
 number = {2},
 year = {2003},
 issn = {0018-9340},
 pages = {139--149},
 doi = {http://dx.doi.org/10.1109/TC.2003.1176982},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
 }

@inproceedings{AHKV03,
  author    = {Micah Adler and
               Eran Halperin and
               Richard M. Karp and
               Vijay V. Vazirani},
  title     = {A stochastic process on the hypercube with applications
               to peer-to-peer networks},
  booktitle = {STOC},
  year      = {2003},
  pages     = {575-584},
}